"""
105. 从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。

 

示例 1:


Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
"""
try:
    from binarytree import Node as TreeNode
    from binarytree import tree
finally:
    from typing import List


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        ...
        if not preorder:
            return None
        root_val = preorder[0]
        root_index = inorder.index(root_val)

        root = TreeNode(root_val)
        root.left = self.buildTree(preorder[1 : root_index + 1], inorder[:root_index])
        root.right = self.buildTree(
            preorder[root_index + 1 :], inorder[root_index + 1 :]
        )

        return root


if __name__ == "__main__":

    my_tree = tree()
    print(my_tree)
    preorder = my_tree.preorder
    preorder = [i.val for i in preorder]
    inorder = my_tree.inorder
    inorder = [i.val for i in inorder]
    s = Solution()
    new_root = s.buildTree(preorder, inorder)
    print(new_root)
